package summary;

import java.util.Arrays;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/11 21:54
 * https://leetcode-cn.com/problems/word-break/
 */
public class Title139 {

    /**
     * 完全背包问题
     * dp[i]表示长度为i的字符串可以拆分出字典中的单词
     * 递推公式：if(dp[j]==true && wordDict.contain(String.substring(j,i+1))) dp[i] = true
     * 初始化：
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        //dp[0]仅仅为了符合推导公式
        dp[0] = true;
        //背包容量
        for (int j = 1; j <= s.length(); j++) {
            for (int i = 0; i < j; i++) {
                if (dp[i] && wordDict.contains(s.substring(i, j))) {
                    dp[j] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }



    /**
     * 回溯 + 记忆化递归
     * @param s
     * @param wordDict
     * @return
     */
    public static boolean wordBreak1(String s, List<String> wordDict) {
        int[] flag = new int[s.length()];
        Arrays.fill(flag, -1);
        return backTracking(s, wordDict, 0, flag);
    }

    private static boolean backTracking(String s, List<String> wordDict, int start, int[] flag) {
        if (start >= s.length()) {
            return true;
        }
        if (flag[start] != -1) {
            return false;
        }
        for (int i = start; i < s.length(); i++) {
            String arr = s.substring(start, i + 1);
            if (wordDict.contains(arr) && backTracking(s, wordDict, i + 1, flag)) {
                flag[start] = 1;
                return true;
            }
        }
        flag[start] = 0;
        return false;
    }



    public boolean wordBreak3(String s, List<String> wordDict) {
        int n = s.length();
        //记录字符串分割的位置，设置为1
        int[] flag = new int[n];
        return dfs(s, n, flag, wordDict, 0);
    }

    private boolean dfs(String s, int n, int[] flag, List<String> wordDict, int cur) {
        if (cur >= n) {
            return true;
        }
        //如果从该点分割记录过，说明此前失败了，直接return false
        if (flag[cur] != 0) {
            return false;
        }
        for (int i = cur; i < n; i++) {
            String splitStr = s.substring(cur, i + 1);
            if (wordDict.contains(splitStr) && dfs(s, n, flag, wordDict, i + 1)) {
                flag[cur] = 1;
                return true;
            }
        }
        flag[cur] = -1;
        return false;
    }


    public static void main(String[] args) {


        List<String> dict = Arrays.asList("a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa");
        wordBreak1("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", dict);
        System.out.println();
    }
}
